package 剑指offer;

import util.LogUtils;

import com.sun.swing.internal.plaf.basic.resources.basic;


/**
 * 动态规划：剪绳子

题目大意

	剑指Offer（第二版）面试题14：剪绳子
	
	题目一：给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],...,k[m].请问k[0]*k[1]*...*k[m]可能的最大乘积是多少？
	
	例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
	
解题思路
	
	思路：首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀时，我们有n-1种选择，也就是说第一段绳子的可能长度分别为1,2,3.....，n-1。因此f(n)=max(f(i)*f(n-i))，其中0<i<n。
	
	这是一个自上而下的递归公式。由于递归会有大量的不必要的重复计算。一个更好的办法是按照从下而上的顺序计算，也就是说我们先得到f(2),f(3)，再得到f(4),f(5)，直到得到f(n)。
	
	当绳子的长度为2的时候，只能剪成长度为1的两段，所以f(2) = 1，当n = 3时，容易得出f(3) = 2;

* 问题分析：  
* 	
* 	递推式：f(n)=max(f(i)*f(n-i))，其中0<i<n。
	http://blog.csdn.net/qq_25827845/article/details/73351134
	@Date 2017-11-11 15：53
 *
 */
public class _014_Solution {
	
	private static final String TAG = "动态规划：剪绳子";

	public int solution(int len) {
		if (len == 0)	return 0;
		if (len == 1)	return 0;
		if (len == 2)	return 1;
		if (len == 3)	return 2;
		
		int[] dp = new int[len+1];
		/*
		 * TODO:这个0,1,2,3是怎么出来的？？？
		 * 
		 *    我的理解是这样的：动态规划，我们首先增加一个特殊情况判断，比如开头分别判断了length = 1,2,3时，返回值为多少，
		 *    	根据f 数组的定义，for循环从i = 4开始，长度为4米的绳子，我们可以剪成2-2和1-3，我们根据这种剪法来确定f 数组前面几个特殊的取值。


		 */
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		
		for (int i = 4; i <= len; i ++) {
			int max = 0;
			for (int j = 1; j <= i/2; j ++) {
				int temp = dp[j]*dp[i-j];
				if (max < temp) 
					max = temp;
				dp[i] = max;
			}
		}
	
		return dp[len];
	}

	
	public static void main(String[] args) {
		System.out.println("what happen>>>"+new _014_Solution().solution(4));
	}
}
